package twice.class_digui;

import java.util.Arrays;

public class Class06_CardFight {

    public static int win1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int first = f1(arr, 0, arr.length - 1);
        int second = g1(arr, 0, arr.length - 1);
        return Math.max(first, second);
    }


    public static int f1(int[] arr,int L,int R){
        if(L==R){
            return arr[L];
        }
        int p1 = arr[L] + g1(arr,L+1,R);
        int p2 = arr[R] + g1(arr,L,R-1);
        return Math.max(p1,p2);
    }

    public static int g1(int[] arr,int L,int R){
        if(L==R){
            return 0;
        }
        int p1 = f1(arr,L+1,R);
        int p2 = f1(arr,L,R-1);
        return Math.min(p1,p2);
    }



    public static int win2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int[][] fmap = new int[arr.length][arr.length];
        int[][] gmap = new int[arr.length][arr.length];
        for(int i = 0; i < arr.length;i++){
            Arrays.fill(fmap[i],-1);
            Arrays.fill(gmap[i],-1);
        }
        int first = f2(arr, 0, arr.length - 1,fmap,gmap);
        int second = g2(arr, 0, arr.length - 1,fmap,gmap);
        return Math.max(first, second);
    }


    public static int f2(int[] arr,int L,int R,int[][] fmap,int[][] gmap){
        if(fmap[L][R]!=-1){
            return fmap[L][R];
        }
        if(L==R){
            fmap[L][R] = arr[L];
            return arr[L];
        }
        int p1 = arr[L] + g2(arr,L+1,R,fmap,gmap);
        int p2 = arr[R] + g2(arr,L,R-1,fmap,gmap);
        int res = Math.max(p1,p2);
        fmap[L][R] = res;
        return res;
    }

    public static int g2(int[] arr,int L,int R,int[][] fmap,int[][] gmap){
        if(gmap[L][R]!=-1){
            return gmap[L][R];
        }
        if(L==R){
            gmap[L][R] = 0;
            return 0;
        }
        int p1 = f2(arr,L+1,R,fmap,gmap);
        int p2 = f2(arr,L,R-1,fmap,gmap);
        int res = Math.min(p1,p2);
        gmap[L][R] = res;
        return res;
    }


    public static int win3(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int[][] fmap = new int[arr.length][arr.length];
        int[][] gmap = new int[arr.length][arr.length];

        for(int i = 0;i<arr.length;i++){
            fmap[i][i] = arr[i];
        }

        for(int Startcol = 1;Startcol<arr.length;Startcol++){
            int i = 0;
            int j = Startcol;
            while(j<arr.length){
                fmap[i][j] = Math.max(arr[i]+gmap[i+1][j],arr[j] + gmap[i][j-1]);
                gmap[i][j] = Math.min(fmap[i+1][j],fmap[i][j-1]);
                i++;
                j++;
            }

        }
        return Math.max(fmap[0][arr.length-1],gmap[0][arr.length-1]);
    }

    public static void main(String[] args) {
        int[] arr = { 5, 7, 4, 5, 8, 1, 6, 0, 3, 4, 6, 1, 7 };
        System.out.println(win1(arr));
        System.out.println(win2(arr));
        System.out.println(win3(arr));

    }
}
